﻿\subsubsection{堆内存管理}

操作系统内核及用户进程在运行过程中，常需要动态的申请内存空间。
例如，内核中维护的线程队列、进程树这些动态数据结构就依赖于动态内存分配策略。
虚拟页面预分配就是一种动态内存分配方式，然而虚拟页面预分配每次分配的内存空间大小为一整个大小为 \KiB{4} 的页面，粒度过大，为此需要引入内存堆。

在 SimpleOS 中，内存堆使用名为 Arena 描述符的结构体描述。
每个 Arena 描述符管理一个或多个连续的、按照固定粒度划分的内存页面。
其声明如下：

\begin{minted}[breakautoindent=true, breaklines]{cpp}
typedef struct __ArenaDescriptor
{
    WORD wGranularity;
    WORD wAvailableUnits;
    LPVOID lpArena;
} ArenaDescriptor, *LPArenaDescriptor, *LPArenaDescriptorTable, *LPHeap;
\end{minted}

\lstinline{wGranularity} 为该描述符管理的虚拟内存页面的粒度，取值范围为 $2^n(4 \le n \le 12)$。


\lstinline{wAvailableUnits} 为该描述符管理的虚拟内存页面中可分配的单元数量，其含义根据粒度不同有所差异。


\lstinline{lpArena} 为该描述符管理的虚拟内存页面起始地址。


当粒度大小为 $2^n(4 \le n \le 7)$ 时（图 \ref{ARENA16}），\lstinline{lpArena} 指向一个虚拟内存页面，即当前描述符管理一个虚拟内存页面，该虚拟内存页面中的低地址部分存放管理各个可分配单元的位图，位图中 \lstinline{0} 表示已占用，\lstinline{1} 表示可分配。
位图实际占用的大小按照粒度大小对齐，例如，粒度为 \Byte{64} 时，一个页面可被划分为 64 个内存块，需要大小为 \Byte{8} 的位图，而实际的位图按照 \Byte{64} 大小存放，多余的 \Byte{56} 空间忽略。
位图自身在位图中也有相应的位标识，例如，粒度为 \Byte{16} 时，存放位图需要 \Byte{32}，即占用两个内存块，因此位图中第 0 位 和第 1 位置为 \lstinline{0}。
\lstinline{wAvailableUnits} 字段记录该描述符中可用的内存块数目。

\begin{figure}[h!]
    \Centering
    \caption{粒度为 \Bytes{16} 的描述符 }
    \label{ARENA16}
    \includegraphics[scale=0.8]{build/Paper/Assets/Arena16.pdf}
\end{figure}

当粒度大小为 $2^n(8 \le n \le 11)$ 时（图 \ref{ARENA256}），\lstinline{lpArena} 指向一个虚拟内存页面，但是虚拟内存页面中不再存放位图，这是因为粒度达到 \Byte{256} 时，存放位图仅需要 \Byte{2}，而 \lstinline{wAvailableUnits} 字段刚好占用一个字的大小。
因此对于这种粒度的描述符，位图直接存放在 \lstinline{wAvailableUnits} 字段中。

\begin{figure}[h!]
    \Centering
    \caption{粒度为 \Bytes{256} 的描述符 }
    \label{ARENA256}
    \includegraphics[scale=0.8]{build/Paper/Assets/Arena256.pdf}
\end{figure}

当粒度达到 $2^{12}$ 时（图 \ref{ARENA4096}），\lstinline{lpArena} 指向一个或多个连续的虚拟内存页面，\lstinline{wAvailableUnits} 中记录虚拟内存页面的个数。
虚拟内存页面中没有额外的信息，全部可供使用。

\begin{figure}[h!]
    \Centering
    \caption{粒度为 \Bytes{4096} 的描述符 }
    \label{ARENA4096}
    \includegraphics[scale=0.8]{build/Paper/Assets/Arena4096.pdf}
\end{figure}

内存堆按照固定的粒度进行分配，申请的内存块大小将被扩大为 $2$ 的整数次幂再行分配。
内存堆是由 Arena 描述符构成的表描述的，分配内存块时遍历堆描述符表，寻找合适粒度的描述符，从 Arena 描述符所管理的页面中分配内存块。
Arena 描述符中的 \lstinline{wGranularity} 取非法值 \lstinline{0} 时，表示该描述符为空描述符，取非法值 \lstinline{1} 时，表示此 Arena 描述符级联到下一层 Arena 描述符表，可据此对内存堆进行扩展。

\subsubsection{堆空间保护}

操作系统堆内存的保护实际上依赖于 CPU 对内存页面的保护。
因此，操作系统的内存保护总体上是以页面为单位的，对于小于一个页面的内存块粒度，操作系统能够进行的保护比较有限。
用户申请到一块堆内存空间后，由于用户对内存块所在的整个页面都具有读写权限，因而可不受限制地读写该内存块以外、当前页面内的内容而不触发 CPU 异常。


由于分配给用户进程的内存总是以页为单位，堆内存管理只是操作系统为用户进程提供的管理方案。
因此即便用户进程进行上述非法的内存读写操作，其影响范围也只局限于用户进程内部，操作系统可视情况对用户的此类行为进行约束。


不同的操作系统由于使用不同的堆内存管理方案，因此对用户程序此类行为的约束方式较为不同。
Windows 操作系统就采用了延迟检测的方案，用户在堆中申请一块内存后，该内存块所在的页面中还保存有堆的其他信息。
若在回收或分配资源时检测到这些信息被污染，则判定用户对非法内存空间进行了写入，进而终止用户进程并报告错误信息。
GNU/Linux 由于采用不同的内存堆管理方案，对用户的此种行为并没严格的限制，操作系统只确保分配给用户进程的堆内存所占页面能够正确回收。


见图 \ref{HEAP_PROTECTION}，本设计中，用户程序运行时的非法写入操作可能会污染粒度较小的 Arena 描述符对应的位图，故而在内存堆分配及回收时进行检测。
分配小粒度的堆内存空间时，需要遍历虚拟页面中存放的位图，由于位图所占空间很少，因此可以以较小的代价统计位图中记录的可用块数量，该数量必须总是与 \lstinline{wAvailableUnits} 字段中记录的值保持一致。
另外，位图自身对应的位图中的位必须始终为 \lstinline{0}，否则说明内存堆描述符已经被非法的内存访问污染。

\begin{figure}[h!]
    \Centering
    \caption{堆空间保护}
    \label{HEAP_PROTECTION}
    \includegraphics[scale=0.8]{build/Paper/Assets/HeapProtection.pdf}
\end{figure}

通过此种方式，可对堆内存块进行有限的保护。
